package com.lwl.Algorithmic_data_structure.class07加强树;


import com.lwl.Algorithmic_data_structure.堆与堆排序.加强堆.Code01_CoverMax;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 线段树，给你一个线段数组，每个元素为一个线段[a,b]
 * 找出重合区域最多所在的线段个数
 */
public class Code01CoverMax {
    public static void main(String[] args) {
        System.out.println("test begin");
        int N = 100;
        int L = 0;
        int R = 200;
        int testTimes = 200000;
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = Code01_CoverMax.generateLines(N, L, R);
            int ans1 = coverMax(lines);
            int ans2 = Code01_CoverMax.maxCover2(lines);
            if (ans1 != ans2) {
                System.out.println("Oops!");
                System.out.println("ans1 : " + ans1);
                System.out.println("ans2 : " + ans2);
                break;
            }
        }
        System.out.println("test end");
    }

    private static class Line {
        int start;
        int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static int coverMax(int[][] arr) {
        // 小根堆，按照起点进行排序
        PriorityQueue<Line> lines = new PriorityQueue<>(Comparator.comparingInt(o -> o.start));
        for (int i = 0; i < arr.length; i++) {
            lines.offer(new Line(arr[i][0], arr[i][1]));
        }
        int maxRes = 0;
        // 大根堆，在新的节点加入时，将【终点小于新节点起点】的节点poll出去
        PriorityQueue<Integer> coverLines = new PriorityQueue<>();
//        PriorityQueue<Line> coverLines = new PriorityQueue<>(Comparator.comparingInt(o -> o.end));
        while (!lines.isEmpty()) {
            Line line = lines.poll();
            while (!coverLines.isEmpty() && line.start >= coverLines.peek()) {
                coverLines.poll();
            }
            coverLines.offer(line.end);
            maxRes = Math.max(coverLines.size(), maxRes);
        }
        return maxRes;
    }

}
